#ifndef __GEEK_COMMANDER_TREE_H_INCLUDED_E399658D_E0F2_45d2_9D11_A4E16A490F6E__
#define __GEEK_COMMANDER_TREE_H_INCLUDED_E399658D_E0F2_45d2_9D11_A4E16A490F6E__

#define GEEK_TREENODE_BLACK 0
#define GEEK_TREENODE_RED 1

template<typename T>
struct geek_treenode
{
    T *left;
    T *right;
    T *parent;
    int color;
    int descendent_count;
};

template<typename T, geek_treenode<T> T::*O>
struct geek_tree
{
    typedef T item_t;
    typedef int (*compare_fn_t)(const item_t *l, const item_t *r);

    item_t *root;
    compare_fn_t compare_fn;

    static geek_treenode<T> *get_treenode(item_t *item)
    {
        if(item == NULL)
        {
            return NULL;
        }
        else
        {
            return &(item->*O);
        }
    }
};

template<typename T>
void geek_tree_create(T *tree)
{
    memset(tree,0,sizeof(T));
}

template<typename T>
void geek_tree_destroy(T *tree)
{
    memset(tree,0,sizeof(T));
}

template<typename T>
void geek_tree_rotate_right(T *tree, typename T::item_t *item)
{
    typedef typename T::item_t item_t;
    typedef geek_treenode<typename T::item_t> node_t;

    node_t *node = T::get_treenode(item);
    item_t *litem = node->left;
    node_t *lnode = T::get_treenode(litem);
    item_t *lritem = lnode->right;
    node_t *lrnode = T::get_treenode(lritem);

    item_t *pitem = node->parent;

    node->descendent_count -= lnode->descendent_count;

    node->left = lritem;
    if(lrnode)
    {
        lrnode->parent = item;
        node->descendent_count += lrnode->descendent_count;
        lnode->descendent_count -= lrnode->descendent_count;
    }

    lnode->right = item;
    node->parent = litem;
    lnode->parent = pitem;

    lnode->descendent_count += node->descendent_count;

    geek_tree_replace_child(tree,item,litem);
}

template<typename T>
void geek_tree_rotate_left(T *tree, typename T::item_t *item)
{
    typedef typename T::item_t item_t;
    typedef geek_treenode<typename T::item_t> node_t;

    node_t *node = T::get_treenode(item);
    item_t *ritem = node->right;
    node_t *rnode = T::get_treenode(ritem);
    item_t *rlitem = rnode->left;
    node_t *rlnode = T::get_treenode(rlitem);
   
    item_t *pitem = node->parent;

    node->descendent_count -= rnode->descendent_count;

    node->right = rlitem;
    if(rlnode)
    {
        rlnode->parent = item;
        node->descendent_count += rlnode->descendent_count;
        rnode->descendent_count -= rlnode->descendent_count;
    }

    rnode->left = item;
    node->parent = ritem;
    rnode->parent = pitem;

    rnode->descendent_count += node->descendent_count;

    geek_tree_replace_child(tree,item,ritem);
}

template<typename T>
void geek_tree_insert(T *tree, typename T::item_t *item)
{
    typedef typename T::item_t item_t;
    typedef geek_treenode<typename T::item_t> node_t;
    node_t *node = T::get_treenode(item);

    // insert node into tree and mark it as red
    {
        item_t *citem = NULL;
        item_t **nextitem = &tree->root;

        while(*nextitem != NULL)
        {
            citem = *nextitem;
            node_t *cnode = T::get_treenode(citem);
            cnode->descendent_count += 1;
            
            if((*tree->compare_fn)(item,citem) < 0)
            {
                nextitem = &cnode->left;
            }
            else
            {
                nextitem = &cnode->right;
            }
        }

        *nextitem = item;
        node->parent = citem;

        node->left = NULL;
        node->right = NULL;
        node->color = GEEK_TREENODE_RED;
        node->descendent_count = 1;
    }

    node_t *nextnode = node;
    while(nextnode != NULL)
    {
        node = nextnode;
        nextnode = NULL;

        node_t *gnode = NULL;
        node_t *unode = NULL;
        node_t *pnode = T::get_treenode(node->parent);

        if(pnode != NULL)
        {
            gnode = T::get_treenode(pnode->parent);
        }

        if(gnode != NULL)
        {
            if(node->parent == gnode->left)
            {
                unode = T::get_treenode(gnode->right);
            }
            else
            {
                unode = T::get_treenode(gnode->left);
            }
        }

        if(pnode == NULL)
        {
            node->color = GEEK_TREENODE_BLACK;
        }
        else if(pnode->color != GEEK_TREENODE_BLACK)
        {
            if(unode != NULL && unode->color == GEEK_TREENODE_RED)
            {
                pnode->color = GEEK_TREENODE_BLACK;
                unode->color = GEEK_TREENODE_BLACK;
                gnode->color = GEEK_TREENODE_RED;
                item = pnode->parent;
                nextnode = gnode;
            }
            else
            {
                if(node == T::get_treenode(pnode->right) && pnode == T::get_treenode(gnode->left))
                {
                    geek_tree_rotate_left(tree,node->parent);
                    item = node->left;
                    node = T::get_treenode(node->left);
                    pnode = T::get_treenode(node->parent);
                    gnode = pnode != NULL ? T::get_treenode(pnode->parent) : NULL;
                }
                else if(node == T::get_treenode(pnode->left) && pnode == T::get_treenode(gnode->right))
                {
                    geek_tree_rotate_right(tree,node->parent);
                    item = node->right;
                    node = T::get_treenode(node->right);
                    pnode = T::get_treenode(node->parent);
                    gnode = pnode != NULL ? T::get_treenode(pnode->parent) : NULL;
                }

                pnode->color = GEEK_TREENODE_BLACK;
                gnode->color = GEEK_TREENODE_RED;

                if(node == T::get_treenode(pnode->left) && pnode == T::get_treenode(gnode->left))
                {
                    geek_tree_rotate_right(tree,pnode->parent);
                }
                else
                {
                    geek_tree_rotate_left(tree,pnode->parent);
                }
            }
        }
    }
}

template<typename T>
void geek_tree_replace_child(T *tree, typename T::item_t *olditem, typename T::item_t *newitem)
{
    typedef geek_treenode<typename T::item_t> node_t;
    node_t *newnode = T::get_treenode(newitem);

    if(newnode->parent != NULL)
    {
        node_t *pnode = T::get_treenode(newnode->parent);
        if(pnode->left == olditem)
        {
            pnode->left = newitem;
        }
        else
        {
            pnode->right = newitem;
        }
    }
    else
    {
        tree->root = newitem;
    }
}

template<typename T>
void geek_tree_swap_item(T *tree, typename T::item_t *oitem, typename T::item_t *ritem)
{
    typedef typename T::item_t item_t;
    typedef geek_treenode<typename T::item_t> node_t;

    node_t *onode = T::get_treenode(oitem);
    node_t *rnode = T::get_treenode(ritem);
    node_t oldonode = *onode;
    node_t oldrnode = *rnode;

    *rnode = oldonode;
    *onode = oldrnode;

    if(rnode->left == ritem)
    {
        rnode->left = oitem;
    }

    if(rnode->right == ritem)
    {
        rnode->right = oitem;
    }

    if(rnode->parent == ritem)
    {
        rnode->parent = oitem;
    }

    if(onode->left == oitem)
    {
        onode->left = ritem;
    }

    if(onode->right == oitem)
    {
        onode->right = ritem;
    }

    if(onode->parent == oitem)
    {
        onode->parent = ritem;
    }

    if(rnode->left != NULL)
    {
        T::get_treenode(rnode->left)->parent = ritem;
    }

    if(rnode->right != NULL)
    {
        T::get_treenode(rnode->right)->parent = ritem;
    }

    if(onode->left != NULL)
    {
        T::get_treenode(onode->left)->parent = oitem;
    }

    if(onode->right != NULL)
    {
        T::get_treenode(onode->right)->parent = oitem;
    }

    geek_tree_replace_child(tree,oitem,ritem);
    geek_tree_replace_child(tree,ritem,oitem);
}

template<typename T>
void geek_tree_replace_parent_item(T *tree, typename T::item_t *olditem, typename T::item_t *newitem)
{
    typedef typename T::item_t item_t;
    typedef geek_treenode<typename T::item_t> node_t;

    node_t *oldnode = T::get_treenode(olditem);
    node_t *newnode = T::get_treenode(newitem);

    if(newnode != NULL)
    {
        newnode->parent = oldnode->parent;
        geek_tree_replace_child(tree,olditem,newitem);

        if(oldnode->left == newitem)
        {
            newnode->left = NULL;
        }
        else
        {
            newnode->left = oldnode->left;
        }

        if(oldnode->right == newitem)
        {
            newnode->right = NULL;
        }
        else
        {
            newnode->right = oldnode->right;
        }

        newnode->descendent_count = oldnode->descendent_count - 1;
    }
    else
    {
        item_t *pitem = oldnode->parent;
        if(pitem != NULL)
        {
            node_t *pnode = T::get_treenode(pitem);
            if(pnode->left == olditem)
            {
                pnode->left = NULL;
            }
            else
            {
                pnode->right = NULL;
            }
        }
        else
        {
            tree->root = NULL;
        }
    }

    {
        node_t *cnode = oldnode;
        while(cnode->parent != NULL)
        {
            node_t *pnode = T::get_treenode(cnode->parent);
            pnode->descendent_count -= 1;
            cnode = pnode;
        }
    }
}

template<typename T>
void geek_tree_remove(T *tree, typename T::item_t *item)
{
    typedef typename T::item_t item_t;
    typedef geek_treenode<typename T::item_t> node_t;
    node_t *node = T::get_treenode(item);

    if(node->left != NULL && node->right != NULL)
    {
        item_t *citem = node->right;
        node_t *cnode = T::get_treenode(citem);

        while(cnode->left != NULL)
        {
            citem = cnode->left;
            cnode = T::get_treenode(citem);
        }

        geek_tree_swap_item(tree,item,citem);
    }

    item_t *citem = node->right == NULL ? node->left : node->right;
    node_t *cnode = T::get_treenode(citem);

    item_t *pitem = node->parent;
    node_t *pnode = T::get_treenode(pitem);
    geek_tree_replace_parent_item(tree,item,citem);
    if(node->color == GEEK_TREENODE_BLACK)
    {
        if(cnode != NULL && cnode->color == GEEK_TREENODE_RED)
        {
            cnode->color = GEEK_TREENODE_BLACK;
        }
        else
        {
            bool done = false;
            item = citem;
            node = T::get_treenode(item);

            while(!done)
            {
                done = true;

                if(pitem != NULL)
                {
                    item_t *sitem = (pnode->left == item ? pnode->right : pnode->left);
                    node_t *snode = T::get_treenode(sitem);

                    if(snode != NULL && snode->color == GEEK_TREENODE_RED)
                    {
                        pnode->color = GEEK_TREENODE_RED;
                        snode->color = GEEK_TREENODE_BLACK;
                        if(item == pnode->left)
                        {
                            geek_tree_rotate_left(tree,pitem);
                        }
                        else
                        {
                            geek_tree_rotate_right(tree,pitem);
                        }
                    }

                    sitem = (pnode->left == item ? pnode->right : pnode->left);
                    snode = T::get_treenode(sitem);
                    item_t *lsitem = snode != NULL ? snode->left : NULL;
                    item_t *rsitem = snode != NULL ? snode->right : NULL;
                    node_t *lsnode = T::get_treenode(lsitem);
                    node_t *rsnode = T::get_treenode(rsitem);

                    if(pnode->color == GEEK_TREENODE_BLACK &&
                        (snode->color == GEEK_TREENODE_BLACK) &&
                        (lsnode == NULL || lsnode->color == GEEK_TREENODE_BLACK) &&
                        (rsnode == NULL || rsnode->color == GEEK_TREENODE_BLACK)
                        )
                    {
                        snode->color = GEEK_TREENODE_RED;
                        item = pitem;
                        node = pnode;
                        pitem = node->parent;
                        pnode = T::get_treenode(pitem);
                        done = false;
                    }
                    else
                    {
                        if(pnode->color == GEEK_TREENODE_RED &&
                            (snode->color == GEEK_TREENODE_BLACK) &&
                            (lsnode == NULL || lsnode->color == GEEK_TREENODE_BLACK) &&
                            (rsnode == NULL || rsnode->color == GEEK_TREENODE_BLACK)
                            )
                        {
                            snode->color = GEEK_TREENODE_RED;
                            pnode->color = GEEK_TREENODE_BLACK;
                        }
                        else
                        {
                            if(snode->color == GEEK_TREENODE_BLACK)
                            {
                                if(item == pnode->left &&
                                    (rsnode == NULL || rsnode->color == GEEK_TREENODE_BLACK) &&
                                    (lsnode != NULL && lsnode->color == GEEK_TREENODE_RED)
                                    )
                                {
                                    snode->color = GEEK_TREENODE_RED;
                                    lsnode->color = GEEK_TREENODE_BLACK;
                                    geek_tree_rotate_right(tree,sitem);
                                }
                                else if(item == pnode->right &&
                                    (lsnode == NULL || lsnode->color == GEEK_TREENODE_BLACK) &&
                                    (rsnode != NULL && rsnode->color == GEEK_TREENODE_RED)
                                    )
                                {
                                    snode->color = GEEK_TREENODE_RED;
                                    rsnode->color = GEEK_TREENODE_BLACK;
                                    geek_tree_rotate_left(tree,sitem);
                                }
                            }

                            sitem = (pnode->left == item ? pnode->right : pnode->left);
                            snode = T::get_treenode(sitem);
                            lsitem = snode != NULL ? snode->left : NULL;
                            rsitem = snode != NULL ? snode->right : NULL;
                            lsnode = T::get_treenode(lsitem);
                            rsnode = T::get_treenode(rsitem);

                            snode->color = pnode->color;
                            pnode->color = GEEK_TREENODE_BLACK;

                            if(item == pnode->left)
                            {
                                rsnode->color = GEEK_TREENODE_BLACK;
                                geek_tree_rotate_left(tree,pitem);
                            }
                            else
                            {
                                lsnode->color = GEEK_TREENODE_BLACK;
                                geek_tree_rotate_right(tree,pitem);
                            }
                        }
                    }
                }
            }
        }
    }
}

template<typename T>
typename T::item_t *geek_tree_find(T *tree, typename T::item_t *item)
{
    typedef typename T::item_t item_t;
    typedef geek_treenode<typename T::item_t> node_t;

    item_t *citem = tree->root;

    while(citem != NULL)
    {
        int r = (*tree->compare_fn)(item,citem);
        if(r == 0)
        {
            return citem;
        }

        node_t *cnode = T::get_treenode(citem);
        citem = (r < 0 ? cnode->left : cnode->right);
    }

    return NULL;
}

template<typename T>
void geek_tree_clear(T *tree)
{
    tree->root = NULL;
}

template<typename T>
typename T::item_t *geek_tree_nth_item(T *tree, int n)
{
    typedef typename T::item_t item_t;
    typedef geek_treenode<typename T::item_t> node_t;

    if(tree->root == NULL ||
        n >= T::get_treenode(tree->root)->descendent_count
        )
    {
        return NULL;
    }

    item_t *citem = tree->root;
    while(citem != NULL)
    {
        node_t *cnode = T::get_treenode(citem);
        int lcount = cnode->left != NULL ? T::get_treenode(cnode->left)->descendent_count : 0;

        if(n < lcount)
        {
            citem = cnode->left;
        }
        else if(n == lcount)
        {
            return citem;
        }
        else
        {
            n -= lcount + 1;
            citem = cnode->right;
        }
    }

    return NULL;
}

#undef GEEK_TREENODE_RED
#undef GEEK_TREENODE_BLACK

#endif // __GEEK_COMMANDER_TREE_H_INCLUDED_E399658D_E0F2_45d2_9D11_A4E16A490F6E__
